package A一周刷爆LeetCode.A基础班.H前缀树和贪心算法;

import java.util.PriorityQueue;

/**
 * @author wei.zhao
 * @description: 中位数
 * @date 2022年03月25日 14:39
 */
public class Code06_MedianQuick {

    public static class MedianHolder {
        //小根堆
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        //大根堆
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>((a, b) -> b - a);

        /* 添加数字 */
        public void addNumber(int num) {
            if (minQueue.isEmpty() || num > minQueue.peek()) {
                minQueue.add(num);
            } else {
                maxQueue.add(num);
            }
            // 判断两个堆是否均衡，移动值到少的堆
            if (Math.abs(minQueue.size() - maxQueue.size()) >= 2) {
                if (minQueue.size() > maxQueue.size()) {
                    maxQueue.add(minQueue.poll());
                } else {
                    minQueue.add(maxQueue.poll());
                }
            }
        }

        /* 获取中位数 */
        public double getMedian() {
            return minQueue.size() == maxQueue.size() ? ((double)(minQueue.peek() + maxQueue.peek()) / 2) : (minQueue.size() > maxQueue.size() ? minQueue.peek() : maxQueue.peek());
        }
    }

    public static void main(String[] args) {
        MedianHolder holder = new MedianHolder();
        holder.addNumber(1);
        holder.addNumber(3);
        holder.addNumber(9);
        holder.addNumber(6);
        holder.addNumber(5);
        holder.addNumber(4);
        holder.addNumber(2);
        holder.addNumber(8);
        holder.addNumber(7);
        System.out.println(holder.getMedian());
    }

}
